package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.Backtracking;
import cn.pugle.oj.catalog.Unknown;

import java.util.*;

/**
 * 错误写法, 引入row等遍历, 导致初始有值的地方不知道要不要走了
 * https://leetcode.com/problems/sudoku-solver/
 *
 * @author tzp
 * @since 2020/10/26
 */
public class LC37 implements Backtracking {
    char[] dict = new char[9];
    char empty = '.';
    int[][] directions = new int[][]{
            {-1, 0},//上
            {0, 1},//右
            {1, 0},//下
            {0, -1},//左
    };

    List<Set<Integer>> row = new ArrayList<>(9);
    List<Set<Integer>> col = new ArrayList<>(9);
    List<Set<Integer>> grid = new ArrayList<>(9);
    boolean hasResult = false;
    boolean[][] path = new boolean[9][9];
    char[][] board;

    public void solveSudoku(char[][] board) {
        this.board = board;
        for (int i = 0; i < 9; i++) {
            dict[i] = (char) ('1' + i);
            row.add(new HashSet<>());
            col.add(new HashSet<>());
            grid.add(new HashSet<>());
        }
        backtracing(0, 0, 0);
    }

    public void backtracing(int x, int y, int validNum) {
        if (board[x][y] != empty) { //原始已有
            set(x, y, board[x][y]);
            if (validNum == 80) {
                hasResult = true;
                return;
            }
            for (int i = 0; i < directions.length; i++) {
                int newX = x + directions[i][0];
                int newY = y + directions[i][1];
                if (validBound(newX, newY) && !path[newX][newY]) {//有效界线, 没走过
                    backtracing(newX, newY, validNum + 1);
                    if (hasResult) {
                        return;
                    }
                }
            }
            //unset( x, y, board[x][y]);//不需要unset
        } else {//原始没有
            for (int i = 0; i < dict.length; i++) {//先为当前格子选择数字
                char choice = dict[i];
                if (validSudoku(x, y, choice)) {
                    set(x, y, choice);
                    if (validNum == 80) {
                        hasResult = true;
                        return;
                    }
                    for (int j = 0; j < directions.length; j++) {
                        int newX = x + directions[j][0];
                        int newY = y + directions[j][1];
                        if (validBound(newX, newY) && !path[newX][newY]) {//有效界线, 没走过
                            backtracing(newX, newY, validNum + 1);
                            if (hasResult) {
                                return;
                            }
                        }
                    }
                    unset(x, y, choice);
                }
            }
        }
    }

    public boolean validBound(int x, int y) {
        return x >= 0 && y >= 0 && x <= 8 && y <= 8;
    }

    public boolean validSudoku(int x, int y, char c) {
        int gridIndex = (x / 3) * 3 + (y / 3);
        return !(row.get(x).contains((int) c)
                || col.get(y).contains((int) c)
                || grid.get(gridIndex).contains((int) c));
    }

    public void set(int x, int y, char c) {
        path[x][y] = true;
        board[x][y] = c;
        row.get(x).add((int) c);
        col.get(y).add((int) c);
        int gridIndex = (x / 3) * 3 + (y / 3);
        grid.get(gridIndex).add((int) c);
    }

    public void unset(int x, int y, char c) {
        path[x][y] = false;
        board[x][y] = empty;
        row.get(x).remove((int) c);
        col.get(y).remove((int) c);
        int gridIndex = (x / 3) * 3 + (y / 3);
        grid.get(gridIndex).remove((int) c);
    }

    public static void main(String[] args) {
        char[][] b = {
                {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {'.', '.', '.', '.', '8', '.', '.', '7', '9'}};
        new LC37().solveSudoku(b);
        System.out.println(Arrays.deepToString(b));
    }
}
